#!/usr/bin/env python
# -*- coding: utf-8 -*-

# 大根堆 - 根 > 子， 递归
def max_heapify_rec(arr, start, end):
    print 'before max_heapify', arr, start, end; 
    root = start; 
    left_child = 2 * root + 1;
    right_child = 2 * root + 2;
    
    # 右子节点超出范围，跳出
    if left_child > end:
        return;
    # 子节点在范围内
    max_child = left_child;
    if right_child <= end and arr[right_child] > arr[max_child]:
        max_child = right_child;
        
    if arr[max_child] > arr[root]:
        # 大的>父  --> 交换，继续循环向下比较
        arr[root], arr[max_child] = arr[max_child], arr[root];
        root = max_child;
        max_heapify_rec(arr, root, end);
    else:
        return;
    print 'after max_heapify', arr, start, end;

def max_heapify(arr, start, end):  
    print 'before max_heapify', arr, start, end;  
    root = start;
    while True:
        child = 2 * root + 1;
        if child > end:
            break;
        if child + 1 <= end and arr[child] < arr[child+1]:
            child += 1;
        if arr[root] < arr[child]:
            arr[root], arr[child] = arr[child], arr[root];
            root = child;
        else:
            break
    print 'after max_heapify', arr, start, end; 
    
# 初始化大根堆       
def max_init(arr):
    # 从最后一个非叶节点开始，向上调整，将最大值交换至最顶
    print '--------max_init start -------';
    print arr;
    length = len(arr);
    first = length / 2 - 1;
    for start in xrange(first, -1, -1):
        max_heapify(arr, start, length-1);
    print arr;
    print '--------max_init end -------';
    
def sort_min_to_max(arr):
    max_init(arr);
    length = len(arr);
    for end in xrange(length-1, 0, -1): # 最后一个元素->[1]
        arr[0], arr[end] = arr[end], arr[0];
        print 'sort:', arr, end;
#         max_heapify_rec(arr, 0, end-1);
        max_heapify(arr, 0, end-1);
        

def main():
    arr = [9, 2, 1, 7, 6, 8, 5, 3, 4];
    sort_min_to_max(arr);
    print arr;  

if __name__ == '__main__':
    main();  